﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphLibrary.Algorithms
{
    sealed public class TopologicalSort<TVertex, TEdge> : GraphAlgorithm<TVertex,TEdge>
        where TEdge : IEdge<TVertex>
    {
        //список топологически упорядоченных вершин
        Stack<TVertex> _list = new Stack<TVertex>();

        public TopologicalSort(IDirectedGraph<TVertex, TEdge> graph)
        {
            Graph = graph;
        }

        public List<TVertex> List
        {
            get
            {
                return _list.ToList<TVertex>();
            }
        }

        public void Execute()
        {
            DepthFirstSearch<TVertex, TEdge> dfs = new DepthFirstSearch<TVertex, TEdge>(Graph);
            dfs.LeaveVertex += delegate(TVertex v)
            {
                _list.Push(v);
            };
            dfs.CycleHasBeenFound += delegate
            {
                throw new GraphException("Graph is cyclic!");
            };
            dfs.Execute();
        }
    }
}
